package com.study.leetcode;

import java.util.HashMap;
import java.util.Map;

public class Solution_852 {
    private static final Map<Integer, Integer> integerMap = new HashMap<>();

    static {
        integerMap.put(0, 1);
        integerMap.put(1, 1);
        integerMap.put(2, 2);
        integerMap.put(3, 5);
    }

    public int numTrees(int n) {
        if (integerMap.get(n) != null) return integerMap.get(n);
        int res = 0;
        for (int i = 0; i < n; i++) {
            int i1 = numTrees(n - i - 1);
            int i2 = numTrees(i);
            res += i1 * i2;
        }
        integerMap.put(n, res);
        return res;
    }

    public static void main(String[] args) {
        Solution_852 solution_852 = new Solution_852();
        solution_852.numTrees(10);
    }
}
